package dynamicProgramming.DoubleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/22 19:58
 **/
/**
 * 题目 ：最长公共子序列
 * 题目详述 ：
 * 给定两个字符串text1 和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 * 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 *
 * 提示：
 * 1 <= text1.length, text2.length <= 1000
 * text1 和 text2 仅由小写英文字符组成。
 */
public class LongestCommonSubsequence03 {
    /**
     * 思路 ：
     * 迭代思想，使用二维数组temp来存储迭代过程中结果;
     * 需要注意的是，若是要去求f(i , j)的值，则只需要知道f(i - 1 ,j) && f(i - 1 , j - 1) && f(i , j - 1)：
     * ===> 所以只需要在二维数组中保存两行数据即可（可以很大程度上减少空间复杂度;）
     *
     * 状态转移方程 ：
     * ===》 假设f(i + 1 , j + 1)为子字符串S[0...i]和T[0...j]的最大字符串长度;
     * （1）若是子字符串S的最后一个字符S[i] == 子字符串T的最后一个字符T[j]，
     * ===》 f(i + 1 , j + 1) = f(i , j) + 1;
     * （2）若是子字符串T的最后一个字符T[j] != 子字符串S的最后一个字符S[i],
     * 即，f(i + 1 , j + 1)就取决于f(i + 1 , j)和f(i , j + 1);
     * ===》 f(i + 1 , j + 1) = max(f(i + 1 , j) , f(i , j + 1));
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        /**
         *  思考 ：为何可以使用一维数组来代替二维数组来实现迭代算法？
         *  原因 ：
         *  要求取f(i + 1 , j + 1)的话，即需要f(i , j) && f(i + 1 , j) && f(i , j + 1);
         *  （1）若是使用二维数组的话，经过空间优化后，也只需要 2行(len2 + 1)列的数组来存储结果;
         *  即，使用temp[j]来存储temp[i - 1][j] && temp[i][j];
         *  （2）实现上述方法所使用的解决方法 ：即，通过cur来记录新生成的temp[j],在计算temp[j]后，再使用temp[j]来存储新纪录;
         *  需要注意的是，prev用来存储temp[j - 1]的旧值;
         *  （3）继续向下遍历temp[j + 1];
         */
        // 使用一维数组，同时需要注意的是 ：temp[0]所存储的是两个子字符串都为空字符串的情况;
        int[] temp = new int[len2 + 1];
        for(int i = 0 ; i < len1 ; i++){
            // 若是要去求取f(i + 1 , j + 1)的话，即需要使用prev变量去存储 f(i , j)的值;
            int prev = temp[0];
            for(int j = 0 ; j < len2 ; j++){
                // 需要注意的是，进入内层for循环时，则temp[j + 1]所存储的值为f(i , j + 1)

                // 使用cur变量去存储f(i + 1 , j + 1)的值：
                int cur;
                // 若是字符串s1的最后一个字符 == 字符串s2的最后一个字符的话，即 cur = prev + 1;
                if(text1.charAt(i) == text2.charAt(j)){
                    cur = prev + 1;
                }
                // 若是不相等的话，即 cur = Math.max(temp[j], temp[j + 1]);
                else {
                    cur = Math.max(temp[j], temp[j + 1]);
                }
                // 使用prev变量来存储f(i , j + 1);
                prev = temp[j + 1];
                // 将temp[j + 1]更新为f(i + 1 , j + 1);
                temp[j + 1] = cur;
            }
        }
        // 返回，即直接返回temp数组最后一个元素即可;
        return temp[len2];
    }
}
